#include <stdio.h>
// 1.查找第一个和最后一个位置
// 给定一个按照升序排列的整数数组和一个目标值，找到目标值在数组中的起始位置和结束位置。如果目标值不存在于数组中，则返回 [-1,-1]。
// 示例:输入数组[5,7,7,8,8,10]和目标值 8，输出[3,4]。
#include <stdio.h>

int main()
{
    int arr[] = {5, 7, 7, 8, 8, 10};
    int n = 8;
    int size = sizeof(arr) / sizeof(arr[0]);
    int result[2] = {-1, -1}; // 初始化为 [-1, -1]

    // 1. 查找左边界（第一个等于 n 的位置）
    int left = 0, right = size - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;    //不安全写法： mid = (left + right) / 2
        if (arr[mid] < n)
        {
            left = mid + 1;
        }
        else if (arr[mid] > n)
        {
            right = mid - 1;
        }
        else
        {
            result[0] = mid; 
            right = mid - 1;
        }
    }

    // 2. 查找右边界（最后一个等于 n 的位置）
    if (result[0] != -1)
    { 
        left = 0;
        right = size - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (arr[mid] < n)
            {
                left = mid + 1;
            }
            else if (arr[mid] > n)
            {
                right = mid - 1;
            }
            else
            {
                result[1] = mid; 
                left = mid + 1;
            }
        }
    }

    printf("[%d, %d]\n", result[0], result[1]);
    return 0;
}






// int main()
// {
//     int arr[6] = {5, 7, 7, 8, 8, 10};
//     int n = 8;
//     int length = sizeof(arr) / sizeof(int);
//     int left = 0;
//     int result[2] = {-1, -1};
//     int right = length - 1;
//     while (left <= right)
//     {
//         int mid = (left + right) / 2;
//         if (n > arr[mid])
//         {
//             left = mid + 1;
//         }
//         else if (n < arr[mid])
//         {
//             right = mid - 1;
//         }
//         else
//         {
//             result[0] = mid;
//         }
//     }
//     // 查找左边是否还有目标数
//     int a = result[0];
//     while (a >= 0)
//     {
//         a--;
//         if (arr[result[0]] == arr[a])
//         {
//             result[0] = a;
//             break;
//         }
//     }
//     // 查找最后一个目标数位置
//     int b = result[0];
//     while (b < (length - 1))
//     {
//         if (arr[b] == arr[b + 1])
//         {
//             result[1] = b;
//             break;
//         }
//         else
//         {
//             result[1] = result[0];
//         }
//         b++;
//     }
//     printf("[%d,%d]", result[0], result[1]);
// }